package basic.study.wantOffer.chapter5;

/**
 * @ClassName Problem43
 * @Description 1-n个整数中1出现次数，参考题解：https://blog.csdn.net/u013132035/article/details/80768636
 * @Company inspur
 * @Author Kevin
 * @Date 2020/5/25 11:32
 * @Version 1.0
 */
public class Problem43 {


    public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;
        for (int i = 1; i <= n; i*= 10) {//i代表位数
            int high = n / (i * 10);//更高位的数字
            int low = (n % i);///更低位的数字
            int cur = (n / i) % 10;//当前位数字
            if (cur == 0) {
                count += high * i;
            } else if (cur == 1) {
                //i的意思是当前位，也就是剩下的当前位数中选择其中一位是1.有i种可能；
                count += high * i + (low + 1);
            } else {
                count += (high + 1) * i;
            }
        }
        return count;
    }

    public int NumberOf1Between1AndN(int n) {
        int count = 0;
        for (int i = 1; i <=n; i *= 10) {
            int high = n / (i * 10);
            int low = n % i;
            int cur = (n / i) % 10;
            if (cur == 0) {
                count += high * i;
            } else if (cur == 1) {
                count += high * i + (low + 1);
            } else {
                count += (high + 1) * i;
            }
        }
        return count;
    }

    //最简单的，单个判断1
    int NumberOf1(int num) {
        int count = 0;
        while (num != 0) {
            if (num % 10 == 1) {
                count++;
            }
            num /= 10;
        }
        return count;
    }


    public int NumberOfXBetween1AndN(int n, int x) {
        if (n < 0|| x < 0|| x > 9) {
            return 0;
        }
        int count = 0;
        for (int i = 1; i <= n; i*= 10) {
            int high = n / (i * 10);
            int low = n % i;
            int cur = (n / i) % 10;
            if (cur == x) {//等于x
                count += high * i + (low + 1);
            } else if(cur > x) {//大于x
                count += (high+1) * i;
            } else {//小于x
                count += high * i;
            }
        }
        return count;
    }
}
